class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

import collections
class Solution(object):
    def getAllElements(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: List[int]
        """
        stack1 = collections.deque()
        while root1:
            stack1.append(root1)
            root1 = root1.left
        stack2 = collections.deque()
        while root2:
            stack2.append(root2)
            root2 = root2.left
        out = []
        while stack1 or stack2:
            if stack1:
                if stack2:
                    if stack1[-1].val < stack2[-1].val:
                        node = stack1.pop()
                        out.append(node.val)
                        if node.right:
                            node = node.right
                            while node:
                                stack1.append(node)
                                node = node.left
                    else:
                        node = stack2.pop()
                        out.append(node.val)
                        if node.right:
                            node = node.right
                            while node:
                                stack2.append(node)
                                node = node.left
                else:
                    node = stack1.pop()
                    out.append(node.val)
                    if node.right:
                        node = node.right
                        while node:
                            stack1.append(node)
                            node = node.left
            else:
                node = stack2.pop()
                out.append(node.val)
                if node.right:
                    node = node.right
                    while node:
                        stack2.append(node)
                        node = node.left
        return out